package cn.cxq.learning.single_linked_list;

import java.util.ArrayList;

/**
 * 剑指offer
 * 链表中倒数第k个结点
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：59697
 * 本题知识点： 链表
 *  算法知识视频讲解
 * 题目描述
 * 输入一个链表，输出该链表中倒数第k个结点。
 * 如果该链表长度小于k，请返回空。
 * 示例1
 * 输入
 * 复制
 * {1,2,3,4,5},1
 * 返回值
 * 复制
 * {5}
 *
 */
public class FindKthToTail {

    // 需要遍历两次，第一次记个数，第二次找倒数
    public ListNode FindKthToTail(ListNode pHead, int k) {

        if (pHead == null || k == 0) {
            return null;
        }

        int count = 0;

        ListNode temp = pHead;

        while (temp!=null) {
            count ++ ;
            temp = temp.next;
        }

        if (count < k) {
            return null;
        }

        temp = pHead;

        for (int i = 0; i < count - k; i++) {
            temp = temp.next;
        }

        return temp;
    }

    // 使用arraylist
//    public ListNode FindKthToTail(ListNode pHead, int k) {
//
//        if (pHead == null || k == 0) {
//            return null;
//        }
//
//        ArrayList<ListNode> list = new ArrayList<>();
//
//        ListNode cur = pHead;
//
//        while (cur != null) {
//            list.add(cur);
//            cur = cur.next;
//        }
//
//        if (k > list.size()) {
//            return null;
//        }
//
//        return list.get(list.size() - k);
//    }

    // 写成反转的了
//    public ListNode FindKthToTail (ListNode pHead, int k) {
//
//        if (pHead == null) {
//            return null;
//        }
//        // write code here
//        ListNode head = new ListNode(Integer.MIN_VALUE); // 辅助指针
//
//        ListNode cur = pHead;
//        ListNode after = cur.next;
//
//        int count = 0;
//
//        while (after!=null) {
//            cur.next = head.next;
//            head.next = cur;
//            cur = after;
//            after = cur.next;
//            count++;
//        }
//
//        cur.next = head.next;
//        head.next = cur;
//        count++;
//
//        if (count < k) {
//            return null;
//        }
//
//        cur = head;
//
//        while (k >0) {
//            cur = cur.next;
//            k--;
//        }
//
//        return cur;
//    }
}
